<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>优化版本的计数排序</title>
</head>
<body>
  <script type="text/javascript">
    function countSort(array) {
      // 1.得到数列的最大值和最小值，并算出差值d
      let min = array[0];
      let max = array[0];
      for (let i = 1; i < array.length; i++) {
        if (array[i] > max) {
          max = array[i];
        } 
        if (array[i] < min) {
          min = array[i];
        }
      }
      const d = max - min;
      // 2.创建统计数组并统计对应元素的个数
      const countArray = new Array(d + 1).fill(0);
      for (let i = 0; i < array.length; i++) {
        // 数列的最小值作为一个偏移量，用于计算整数在统计数组中的下标
        countArray[array[i] - min]++;
      }
      // 3.统计数组做变形，后面的元素等于前面的元素之和
      for (let i = 1; i < countArray.length; i++) {
        countArray[i] += countArray[i - 1];
      }
      // 4.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
      const sortedArray = new Array(array.length).fill(0);
      for (let i = array.length - 1; i >= 0; i--) {
        const offset = array[i] - min;
        sortedArray[countArray[offset] - 1] = array[i];
        countArray[offset]--;
      }
      return sortedArray;
    }

    const arr = [10, 6, 3, 4, 8, 1, 2];
    console.log(countSort(arr));
  </script>
</body>
</html>